package LeetCode.tree;

public class LC_105 {
    private int i = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int begin = 0, end = inorder.length;
        TreeNode root = buildChildTree(preorder, inorder, begin, end-1);
        return root;
    }
    public TreeNode buildChildTree(int[] preorder, int[] inorder, int begin, int end){
        if(begin > end){
            return null;
        }
//        if(i == preorder.length){
//            return null;
//        }
        TreeNode root = new TreeNode(preorder[i]);
        int index = findIndex(inorder,begin,end,preorder[i]);
        i++;
        root.left = buildChildTree(preorder, inorder, begin, index-1);
        root.right = buildChildTree(preorder, inorder, index+1,end);
        return root;
    }
    public int findIndex(int[] preorder,int begin, int end, int val){
        while (begin <= end){
            if(preorder[begin] == val){
                return begin;
            }
            begin++;
        }
        return -1;
    }

    public static void main(String[] args) {
        LC_105 n = new LC_105();
        int[] arr1 = {3,9,20,15,7};
        int[] arr2 = {9,3,15,20,7};
        TreeNode root = n.buildTree(arr1,arr2);
        System.out.println(root.data);
    }
}
